package top.minuy.structure.graph.path.bfs;
import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;

/**
 * 多路径规划，广度优先遍历
 *
 * @author Minuy
 * @time 10:01
 * @date 2021/11/20
 */
public class AllPairsPath {

    private Graph g;
    private SingleSourcePath[] paths;

    public AllPairsPath(Graph g) {
        this.g = g;

        paths = new SingleSourcePath[g.V()];
        for (int v = 0; v < g.V(); v++) {
            paths[v] = new SingleSourcePath(g, v);
        }

    }

    /**
     * 查询两个顶点之间相连不
     *
     * @param v 顶点1
     * @param w 顶点2
     * @return boolean 是否相连
     * @author Minuy
     * @date 2021/11/16 23:48
     */
    public boolean isConnected(int v, int w) {
        g.validateVertex(v);
        return paths[v].isConnectedTo(w); // 在这个函数中有对w的校验
    }

    /**
     * 求任意两点之间的路径
     *
     * @param s 源顶点
     * @param t 目标顶点
     * @return Iterable<Integer> 源顶点到目标顶点的路径
     * @author Minuy
     * @date 2021/11/16 23:50
     */
    public Iterable<Integer> path(int s, int t) {
        g.validateVertex(s);
        g.validateVertex(t);

        if (!isConnected(s,t)){
            // 如果不在一个联通分量里，直接返回空列表
            return new ArrayList<>();
        }

        // 返回其路径
        return paths[s].path(t);
    }

}
